#include <iostream>
#include <vector>
#include <climits>
#include <algorithm> 
std::pair<int, int> findMinAndSecondMin(const std::vector<int>& arr, int left, int right) {
    if (left == right) {
        throw std::invalid_argument("Array segment must contain at least two distinct elements");
    }
    if (left + 1 == right) {
        return {std::min(arr[left], arr[right]), std::max(arr[left], arr[right])};
    }
    int mid = left + (right - left) / 2;
    auto leftPair = findMinAndSecondMin(arr, left, mid);
    auto rightPair = findMinAndSecondMin(arr, mid, right);

    int overallMin = std::min(leftPair.first, rightPair.first);
    int overallSecondMin = (leftPair.first == overallMin) ? std::min(leftPair.second, rightPair.first) :
                           (rightPair.first == overallMin) ? std::min(leftPair.first, rightPair.second) :
                           std::min(leftPair.second, rightPair.second);
    if (overallSecondMin == overallMin) {
        int candidateLeft = (leftPair.first == overallMin) ? (leftPair.second == overallMin ? INT_MAX : leftPair.second) : leftPair.first;
        int candidateRight = (rightPair.first == overallMin) ? (rightPair.second == overallMin ? INT_MAX : rightPair.second) : rightPair.first;
        overallSecondMin = std::min(candidateLeft, candidateRight);
    }
    return {overallMin, overallSecondMin};
}
int secondMin(const std::vector<int>& arr) {
    if (arr.size() < 2) {
        throw std::invalid_argument("Array must contain at least two elements");
    }
    return findMinAndSecondMin(arr, 0, arr.size()).second;
}
int main() {
    std::vector<int> arr = {3, 1, 2, 3, 4, 0, 5};
    try {
        int secondMinValue = secondMin(arr);
        std::cout << "The second minimum value in the array is: " << secondMinValue << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }
    return 0;
}